#region Summary

// 
// Owner : JackieHan 
// 
// Solution : LearnSolution 
// 
// Project : JackieHan.ArithmeticCollect 
// 
// File : SerialNumberSummation.cs 
// 
// CopyRight : Copyright © 2009-2010 JackieHan Personal, All Rights Reserved 
// 
// Summary : 给定正整数有可能被表式为n(n>2)个正整数之和 
// 
// History : 
//			2010-05-21 14:36:48	    Create 
// 

#endregion

#region Using

using System;
using System.Collections.Generic;

#endregion

namespace JackieHan.ArithmeticCollect
{
    /// <summary> 
    /// 给定正整数有可能被表式为n(n>2)个正整数之和 
    /// </summary> 
    /// <example>
    /// 例如
    ///     15=1+2+3+4+5
    ///     15=4+5+6
    ///     15=7+8
    /// </example>
    /// <remarks>
    /// 设计一算法找出给定正整数的所有组合
    /// </remarks>
    public class SerialNumberSummation
    {

        /// <summary>
        /// 获取所有组合
        /// </summary>
        /// <param name="number">输入的正整数</param>
        public static void GetAllSerialsOne(int number)
        {
            int divisor = 0;    //除数
            int remainder = 0;//余数
            int count = 2;//假设是几个连续的正整数之和  从2开始
            do
            {
                divisor = number/count;
                remainder = number%count;
                //如果是偶数个正整数之和，则余数必须为个数的一半
                //例如：15=7+8   15/2=7余1
                if (divisor >= count/2 && count%2 == 0 && remainder == count/2)
                {
                    for (int i = 0; i < count; i++)
                    {
                        Console.Write(divisor - count/2 + 1 + i);
                        Console.Write(" ");
                    }
                    Console.WriteLine();
                }
                    //如果是奇数个正整数之和，则余数必须等0
                    //例如：15=4+5+6   15/3=5余0
                else if (divisor - 1 > count/2 && remainder == 0 && count%2 == 1)
                {
                    for (int i = 0; i < count; i++)
                    {
                        Console.Write(divisor - count/2 + i);
                        Console.Write(" ");
                    }
                    Console.WriteLine();
                }
                count++;
                //} while (count < number / 2);
            } while (count*(count + 1)/2 <= number); 

            Console.WriteLine("循环了{0}次", count - 2);
        }

        /// <summary>
        /// 获取所有组合
        /// </summary>
        /// <param name="number">输入的正整数</param>
        /// <remarks>
        /// 推导过程：
        /// 假如起始数为n，从n开始累加到m+n和为s
        /// s=(n+n+m)*(m+1)/2  ==>
        /// n=s/(m+1)-m/2      ==>n和m成反比，m越大则n会越来越小，当n小于1的时候，查找结束
        /// n=(2s-m*(m+1))/(2*(m+1))
        /// </remarks>
        public static void GetAllSerialsTwo(int number)
        {
            int startNumber = 0;
            int count = 1;
            do
            {
                int up = 2 * number - count * (count + 1);
                int down = 2 * (count + 1);

                startNumber = up / down;

                if (up % down == 0 && startNumber > 0)
                {
                    for (int i = startNumber; i <= startNumber + count; i++)
                    {
                        if (i == startNumber)
                        {
                            Console.Write(i);
                        }
                        else
                        {
                            Console.Write(string.Format("+{0}", i));
                        }
                    }
                    Console.WriteLine();
                }
                count++;
            } while (startNumber > 0);

            Console.WriteLine("循环了{0}次", count - 1);
        }


//        进一步优化
//下面我就来谈谈如何进一步优化。其实上周那篇文章的评论中已经有人发现了奇数和偶数的问题，但还是没有深入的进行推导演化，最终无法解开这个谜团。
//首先我们先看 m 为 奇数时，即 m = 2k + 1 (k>=0) ，将 2k+1 带入上面我们已经导出的公式
//s = (n + n + m) * (m+1) / 2;  则
//s = (2n + 2k + 1) * (2k + 2) /2 = (2n + 2k +1)*(K+1) = 2(n+k)*(k+1) + k + 1
//由于 2(n+k)*(k+1) 肯定是偶数，这时我们发现当 k 为 奇数时 s 肯定是偶数，而k为偶数时，s肯定是奇数
//由于 s 是已知的，所以我们只需要遍历 m为3,7,11 … 或者m 为 1,5,9… 这两种序列中的一种序列。这个规律诺贝尔在上一篇的回复中已经发现，可以减少运算量1/4。
//然后我们再看 m 为偶数的情况，即 m = 2(k+1) (k >= 0)
//s = (2n + 2(k+1))*(2(k+1)+1)/2 = (n + k + 1) * (2k + 3)
//这时我们发现，m 为偶数时，s的奇偶情况由n 和 k 共同决定，这种情况，我们用上面分析m为奇数时的思路已经不好用，我们必须换一种考虑问题的方法。
//我们发现要使n 为一个整数值， s 必须可以被2k+3整除，也就是说 s 必须能被大于等于3的奇数整除，我们可以把问题转换为如何快速的找到这些可以被s整除的奇数上。
//如何快速找到这些奇数呢？这个地方又要用到一些数学知识了。
//我们知道任何一个大于等于3的奇数都可以分解为1个或n个大于等于3的质数的乘积。
//比如 3 = 3 , 5 = 5, 7=7, 9 = 3*3, 11=11,13=13,15=3*5
//我上面说的这个定理是很容易证明的，证明过程我就不写了，有兴趣的人可以自己去证明。
//这样我们的问题就化解为寻找这个质数的组合，把一个大于等于3的奇数分解为n个大于等于3的质数的乘积，其中n > 0
//质数在整数序列中占的比例很小，这可以让我们减少大量的计算量。(素数我们可以预先找出来放到一个数组中)
//找到这个质数的组合后，我们从小到大来相乘，并设置一个上限，这个上限诺贝尔 已经推导出是 2s 的平方根，这样可以以非常小的计算量算出所有满足条件的m。

    }
}
